#! /usr/bin/python3
# -*- coding: UTF-8 -*-
  
'''※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※
File Name: backtracking.py
Author: GID5564
Description: 回溯法解决问题，皇后，独数
Version: 1.0
Created Time: 27/11/24-08:53:01
※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※'''

"""
    当我们想确定从1到n的所有可能的k个数的组合。我们使用回溯法来解决这个问题。
    时间复杂度：O(C(n,k)) 即 O(n choose k) = O((n!/(k! * (n - k)!)))
"""

def generate_all_combinations(n: int, k: int) -> [[int]]:
    """
    生成所有从1到n中选择k个数的组合。
    
    参数:
    n (int): 范围的上限（包含）。
    k (int): 组合中数字的数量。
    
    返回:
    [[int]]: 所有可能的组合列表。
    
    示例:
    >>> generate_all_combinations(n=4, k=2)
    [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
    """
    result = []  # 存储所有组合的结果列表
    create_all_state(1, n, k, [], result)  # 调用辅助函数生成组合
    return result  # 返回结果列表

def create_all_state(increment, total_number, level, current_list, total_list):
    """
    递归地生成所有可能的组合。
    
    参数:
    increment (int): 当前起始数字。
    total_number (int): 范围的上限。
    level (int): 还需要选择的数字数量。
    current_list ([int]): 当前组合的临时列表。
    total_list ([[int]]): 存储所有组合的最终列表。
    """
    if level == 0:  # 如果不需要再选择数字了，将当前组合加入结果列表
        total_list.append(current_list[:])  # 深拷贝当前组合并加入结果列表
        return  # 结束当前递归分支

    for i in range(increment, total_number - level + 2):  # 遍历可能的选择
        current_list.append(i)  # 将当前数字加入组合
        create_all_state(i + 1, total_number, level - 1, current_list, total_list)  # 递归调用生成剩余组合
        current_list.pop()  # 回溯，移除最后一个数字以尝试其他组合


"""
#例:
def print_all_state(total_list):
    #打印所有组合。
    #参数:
    #    total_list ([[int]]): 需要打印的组合列表。
    
    for i in total_list:  # 遍历每个组合
        print(*i)  # 打印组合中的数字
if __name__ == "__main__":
    n = 4  # 设置范围上限为4
    k = 2  # 设置组合中数字的数量为2
    total_list = generate_all_combinations(n, k)  # 生成所有组合
    print_all_state(total_list)  # 打印所有组合
"""




"""
    当我们想确定给定序列的所有可能排列。我们使用回溯法来解决这个问题。

    时间复杂度：O(n! * n)，其中n表示给定序列的长度。
"""

def generate_all_permutations(sequence):
    # 调用辅助函数创建状态空间树并开始生成排列
    create_state_space_tree(sequence, [], 0, [False for i in range(len(sequence))])

def create_state_space_tree(sequence, current_sequence, index, index_used):
    """
        创建一个状态空间树，通过深度优先搜索（DFS）遍历每个分支。
        我们知道每个状态都有恰好 len(sequence) - index 个子节点。
        当到达给定序列的末尾时终止。
    """

    # 如果当前索引等于序列长度，说明已经生成了一个完整的排列
    if index == len(sequence):
        print(current_sequence)
        return

    # 遍历序列中的每个元素
    for i in range(len(sequence)):
        if not index_used[i]:  # 如果该元素尚未被使用
            current_sequence.append(sequence[i])  # 将该元素添加到当前排列中
            index_used[i] = True  # 标记该元素已被使用
            # 递归调用，继续生成下一个位置的元素
            create_state_space_tree(sequence, current_sequence, index + 1, index_used)
            current_sequence.pop()  # 回溯，移除最后一个元素
            index_used[i] = False  # 取消标记，以便其他分支可以使用该元素

"""
    取消注释以从用户获取输入

    print("Enter the elements")
    sequence = list(map(int, input().split()))


# 示例输入1：整数列表
sequence = [3, 1, 2, 4]
generate_all_permutations(sequence)

# 示例输入2：字符列表
sequence = ["A", "B", "C"]
generate_all_permutations(sequence)

"""
    
 
"""
    当我们想确定给定序列的所有可能子序列。我们使用回溯法来解决这个问题。

    时间复杂度：O(2^n)，
    其中 n 表示给定序列的长度。
"""

def generate_all_subsequences(sequence):
    # 调用辅助函数创建状态空间树并开始生成子序列
    create_state_space_tree(sequence, [], 0)

def create_state_space_tree(sequence, current_subsequence, index):
    """
        创建一个状态空间树，通过深度优先搜索（DFS）遍历每个分支。
        我们知道每个状态都有两个子节点。
        当到达给定序列的末尾时终止。
    """

    # 如果索引达到序列长度，打印当前子序列并返回
    if index == len(sequence):
        print(current_subsequence)
        return

    # 不包含当前元素的子序列
    create_state_space_tree(sequence, current_subsequence, index + 1)
    
    # 包含当前元素的子序列
    current_subsequence.append(sequence[index])
    create_state_space_tree(sequence, current_subsequence, index + 1)
    
    # 回溯，移除最后一个元素以尝试其他可能性
    current_subsequence.pop()

"""
    取消注释以从用户获取输入

    print("Enter the elements")
    sequence = list(map(int, input().split()))

# 示例输入1：整数列表
sequence = [3, 1, 2, 4]
generate_all_subsequences(sequence)

# 示例输入2：字符列表
sequence = ["A", "B", "C"]
generate_all_subsequences(sequence)
  
"""



def minimax(Depth, nodeIndex, isMax, scores, height):
    """
    实现一个minimax算法，用于在给定的树形结构中找到最优解。

    参数:
    Depth (int): 当前节点的深度。
    nodeIndex (int): 当前节点的索引。
    isMax (bool): 当前节点是否为最大化玩家。
    scores (list): 存储所有叶子节点分数的列表。
    height (int): 树的高度。

    返回值:
    int: 当前节点的最优分数。
    """

    # 如果当前深度等于树的高度，说明已经到达叶子节点，直接返回该节点的分数
    if Depth == height:
        return scores[nodeIndex]

    # 如果当前节点是最大化玩家，则选择子节点中的最大值
    if isMax:
        return max(
            minimax(Depth + 1, nodeIndex * 2, False, scores, height),  # 递归调用左子节点，切换到最小化玩家
            minimax(Depth + 1, nodeIndex * 2 + 1, False, scores, height)  # 递归调用右子节点，切换到最小化玩家
        )
    
    # 如果当前节点是最小化玩家，则选择子节点中的最小值
    return min(
        minimax(Depth + 1, nodeIndex * 2, True, scores, height),  # 递归调用左子节点，切换到最大化玩家
        minimax(Depth + 1, nodeIndex * 2 + 1, True, scores, height)  # 递归调用右子节点，切换到最大化玩家
    )

"""
#例:
if __name__ == "__main__":

    scores = [90, 23, 6, 33, 21, 65, 123, 34423]
    height = math.log(len(scores), 2)

    print("Optimal value : ", end="")
    print(minimax(0, 0, True, scores, height))

"""
    
    
    
    
def isSafe(board, row, column):
    """
    判断在当前棋盘状态下，是否可以在指定位置放置皇后。

    参数:
    board (2D 矩阵): 棋盘状态
    row, column (int): 棋盘上的坐标

    返回值:
    bool: 如果可以安全放置皇后则返回 True，否则返回 False
    """
    # 检查同一行是否有其他皇后
    for i in range(len(board)):
        if board[row][i] == 1:
            return False
    
    # 检查同一列是否有其他皇后
    for i in range(len(board)):
        if board[i][column] == 1:
            return False
    
    # 检查左上对角线是否有其他皇后
    for i, j in zip(range(row, -1, -1), range(column, -1, -1)):
        if board[i][j] == 1:
            return False
    
    # 检查右上对角线是否有其他皇后
    for i, j in zip(range(row, -1, -1), range(column, len(board))):
        if board[i][j] == 1:
            return False
    
    # 如果以上条件都不满足，说明可以安全放置皇后
    return True
    
solution = []

def solve(board, row):
    """
    该函数创建一个状态空间树，并调用 safe 函数直到接收到 False 布尔值，
    然后终止该分支并进行回溯以尝试下一个可能的解决方案分支。
    
    参数:
    board (list of list of int): 棋盘的当前状态，0 表示空位，1 表示皇后。
    row (int): 当前正在处理的行号。
    
    返回:
    bool: 如果找到解决方案则返回 True，否则返回 False。
    """
    # 如果当前行号超过了棋盘的大小，说明已经成功放置了所有皇后
    if row >= len(board):
        # 将成功的棋盘组合添加到解决方案列表中
        solution.append(board)
        # 打印当前成功的棋盘组合
        printboard(board)
        print()
        return True
    
    # 遍历当前行的每一列，检查是否可以在该位置放置皇后
    for i in range(len(board)):
        # 如果可以安全地在 (row, i) 位置放置皇后
        if isSafe(board, row, i):
            # 在 (row, i) 位置放置皇后
            board[row][i] = 1
            # 递归调用 solve 函数处理下一行
            if solve(board, row + 1):
                return True
            # 回溯：移除 (row, i) 位置的皇后
            board[row][i] = 0
    
    # 如果当前行的所有列都不能放置皇后，则返回 False
    return False
    
def printboard(board):
    """
    打印棋盘上成功的组合。
    
    参数:
    board (list of list of int): 一个二维列表，表示棋盘，其中1表示皇后的位置，0表示空位。
    
    返回值:
    None
    """
    # 遍历棋盘的每一行
    for i in range(len(board)):
        # 遍历当前行的每一列
        for j in range(len(board[i])):
            # 如果当前位置是皇后（值为1），则打印"Q"
            if board[i][j] == 1:
                print("Q", end=" ")
            # 否则打印"."
            else:
                print(".", end=" ")
        # 每打印完一行后换行
        print()
"""
#例:
# n=int(input("The no. of queens"))
n = 8
board = [[0 for i in range(n)] for j in range(n)]
solve(board, 0)
print("The total no. of solutions are :", len(solution))
"""


# assigning initial values to the grid
initial_grid = [
    [3, 0, 6, 5, 0, 8, 4, 0, 0],
    [5, 2, 0, 0, 0, 0, 0, 0, 0],
    [0, 8, 7, 0, 0, 0, 0, 3, 1],
    [0, 0, 3, 0, 1, 0, 0, 8, 0],
    [9, 0, 0, 8, 6, 3, 0, 0, 5],
    [0, 5, 0, 0, 9, 0, 6, 0, 0],
    [1, 3, 0, 0, 0, 0, 2, 5, 0],
    [0, 0, 0, 0, 0, 0, 0, 7, 4],
    [0, 0, 5, 2, 0, 6, 3, 0, 0],
]

# a grid with no solution
no_solution = [
    [5, 0, 6, 5, 0, 8, 4, 0, 3],
    [5, 2, 0, 0, 0, 0, 0, 0, 2],
    [1, 8, 7, 0, 0, 0, 0, 3, 1],
    [0, 0, 3, 0, 1, 0, 0, 8, 0],
    [9, 0, 0, 8, 6, 3, 0, 0, 5],
    [0, 5, 0, 0, 9, 0, 6, 0, 0],
    [1, 3, 0, 0, 0, 0, 2, 5, 0],
    [0, 0, 0, 0, 0, 0, 0, 7, 4],
    [0, 0, 5, 2, 0, 6, 3, 0, 0],
]
    
def is_safe(grid, row, column, n):
    """
    检查网格中的每一行、每一列和3x3子网格是否包含数字'n'。
    如果找到重复的数字，则返回False；否则返回True。
    
    参数:
    grid (list of list of int): 9x9的数独网格
    row (int): 当前要检查的行索引
    column (int): 当前要检查的列索引
    n (int): 要检查的数字
    
    返回值:
    bool: 如果该位置安全（没有重复数字），返回True；否则返回False
    """
    # 检查当前行是否有重复的数字
    for i in range(9):
        if grid[row][i] == n:
            return False

    # 检查当前列是否有重复的数字
    for i in range(9):
        if grid[i][column] == n:
            return False

    # 检查3x3子网格是否有重复的数字
    start_row = row - row % 3
    start_col = column - column % 3
    for i in range(3):
        for j in range(3):
            if grid[start_row + i][start_col + j] == n:
                return False

    # 如果没有找到重复的数字，返回True
    return True
def is_completed(grid):
    """
    检查数独是否完成。当所有单元格都被分配了一个非零数字时，数独被认为是完成的。

    参数:
    grid (list of list of int): 表示数独的二维列表，每个元素是一个整数。

    返回值:
    bool: 如果数独完成则返回True，否则返回False。

    示例:
    >>> is_completed([[0]])
    False
    >>> is_completed([[1]])
    True
    >>> is_completed([[1, 2], [0, 4]])
    False
    >>> is_completed([[1, 2], [3, 4]])
    True
    >>> is_completed(initial_grid)
    False
    >>> is_completed(no_solution)
    False
    """
    # 使用嵌套的all函数来检查每一行和每一个单元格是否都不等于0
    return all(all(cell != 0 for cell in row) for row in grid)
    
def find_empty_location(grid):
    """
    查找一个空位置，以便我们可以为该行和列分配一个数字。
    
    参数:
    grid (list of list of int): 9x9的数独网格，其中0表示空位置。
    
    返回值:
    tuple: 包含空位置的行和列索引的元组。如果没有空位置，则返回None。
    """
    for i in range(9):
        for j in range(9):
            if grid[i][j] == 0:
                return i, j
    return None

def sudoku(grid):
    """
    接受一个部分填充的网格，并尝试以符合数独解决方案要求的方式（行、列和盒子中没有重复）
    为所有未分配的位置赋值。
    
    参数:
    grid (list of list of int): 9x9的数独网格，其中0表示空位置。
    
    返回值:
    list of list of int or bool: 如果找到解决方案，则返回解决后的网格；否则返回False。
    """
    # 如果网格已经完成，直接返回网格
    if is_completed(grid):
        return grid

    # 查找一个空位置
    row, column = find_empty_location(grid)
    
    # 如果没有空位置，说明已经填满，返回True表示成功完成
    if row is None and column is None:
        return True

    # 尝试在空位置填入1到9的数字
    for digit in range(1, 10):
        # 检查填入的数字是否安全
        if is_safe(grid, row, column, digit):
            # 将数字填入空位置
            grid[row][column] = digit

            # 递归调用sudoku函数继续解决问题
            if sudoku(grid):
                return grid

            # 如果填入的数字导致无解，回溯，将位置重置为0
            grid[row][column] = 0

    # 如果所有数字都试过了仍然无法解决，返回False
    return False
"""
#例:
def print_solution(grid):
    """
    A function to print the solution in the form
    of a 9x9 grid
    """
    for row in grid:
        for cell in row:
            print(cell, end=" ")
        print()


if __name__ == "__main__":
    # make a copy of grid so that you can compare with the unmodified grid
    for grid in (initial_grid, no_solution):
        grid = list(map(list, grid))
        solution = sudoku(grid)
        if solution:
            print("grid after solving:")
            print_solution(solution)
        else:
            print("Cannot find a solution.")
"""
    
    
    
def generate_sum_of_subsets_soln(nums, max_sum):
    """
    生成所有子集，其元素之和等于给定的最大和。

    参数:
    nums (List[int]): 输入的整数列表。
    max_sum (int): 目标和。

    返回:
    List[List[int]]: 满足条件的所有子集列表。
    """
    result = []  # 存储结果的列表
    path = []  # 当前路径（子集）
    num_index = 0  # 当前处理的数字索引
    remaining_nums_sum = sum(nums)  # 剩余数字的总和
    create_state_space_tree(nums, max_sum, num_index, path, result, remaining_nums_sum)
    return result


def create_state_space_tree(nums, max_sum, num_index, path, result, remaining_nums_sum):
    """
    创建状态空间树以通过深度优先搜索（DFS）迭代每个分支。
    当以下任一条件满足时终止节点的分支：
    1. 当前路径的和大于最大和。
    2. 剩余数字的总和加上当前路径的和小于最大和。
    该算法遵循深度优先搜索并在节点不可分支时回溯。

    参数:
    nums (List[int]): 输入的整数列表。
    max_sum (int): 目标和。
    num_index (int): 当前处理的数字索引。
    path (List[int]): 当前路径（子集）。
    result (List[List[int]]): 存储结果的列表。
    remaining_nums_sum (int): 剩余数字的总和。
    """
    # 如果当前路径的和大于最大和，或者剩余数字的总和加上当前路径的和小于最大和，则终止分支
    if sum(path) > max_sum or (remaining_nums_sum + sum(path)) < max_sum:
        return
    # 如果当前路径的和等于最大和，则将当前路径添加到结果中
    if sum(path) == max_sum:
        result.append(path)
        return
    # 遍历从当前索引到列表末尾的所有数字
    for num_index in range(num_index, len(nums)):
        # 递归调用函数，处理下一个数字，并更新路径和剩余数字的总和
        create_state_space_tree(
            nums,
            max_sum,
            num_index + 1,
            path + [nums[num_index]],
            result,
            remaining_nums_sum - nums[num_index],
        )


"""
#例:

print("Enter the elements")
nums = list(map(int, input().split()))
print("Enter max_sum sum")
max_sum = int(input())

nums = [3, 34, 4, 12, 5, 2]
max_sum = 9
result = generate_sum_of_subsets_soln(nums, max_sum)
print(*result)
"""

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    